//43. 字符串相乘
//思路：将字符反序存入数组里，对应位置上的数字进行相乘并相加，存入另一个数组中
//再转为字符存入另外一个字符串

#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    string multiply(string num1, string num2) {
        vector<int> A, B;
        //num1,num2分别逆序存入数组A，B
        int m = num1.size(), n = num2.size();
        for(int i = m-1; i >= 0; --i)
        {
            A.push_back(num1[i]-'0');
        }
        for(int i = n-1; i >= 0; --i)
        {
            B.push_back(num2[i]-'0');
        }

        //计算每一位，并错位相加
        vector<int> C(m+n);
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                C[i+j] += A[i] * B[j];
            }
        }

        //进位
        int t = 0;
        for(int i = 0; i < C.size(); ++i)
        {
            t += C[i];
            C[i] = t % 10;
            t /= 10;
        }

        //处理前导0
        int k = C.size() - 1;
        while(k > 0 && !C[k])
        {
            k--;
        }

        //逆置并将数字转为字符
        string ret;
        for(int i = k; i >= 0; --i)
        {
            ret += C[i] + '0';
        }

        return ret;
   }
};